package com.linzm.leetcode.primary.exercises2_20230116;

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @Author zimingl
 * @Date 2023/1/18 23:03
 * @Description: 图像渲染 dfs
 */
public class Demo8_733 {
    /**
     * 有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。
     * 你也被给予三个整数 sr ,  sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。
     * 为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 newColor 。
     * 最后返回 经过上色渲染后的图像 。
     */
    public static void main(String[] args) {
        Demo8_733 demo8_733 = new Demo8_733();
        int[][] image = {{1,1,1},{1,1,0},{1,0,1}};
        int sr = 1, sc = 1, newColor = 2;
        int[][] floodFill = demo8_733.floodFill2(image, sr, sc, newColor);
        List<int[]> collect = Stream.of(floodFill).collect(Collectors.toList());
    }

    public int[][] floodFill2(int[][] image, int sr, int sc, int color) {
        if(image[sr][sc] == color) return image;
        int m = image[sr][sc];
        image[sr][sc] = color;
        // 如果不在最上一行
        if (sr != 0 && m == image[sr - 1][sc]) floodFill2(image, sr - 1, sc, color);
        // 如果不在最下一行
        if (sr != image.length - 1 && m == image[sr + 1][sc]) floodFill2(image, sr + 1, sc, color);
        // 如果不在最左一列
        if (sc != 0 && m == image[sr][sc - 1]) floodFill2(image, sr, sc - 1, color);
        // 如果不在最右一列
        if (sc != image[0].length - 1 && m == image[sr][sc + 1]) floodFill2(image, sr, sc + 1, color);
        return image;
    }

    int m;
    int n;
    boolean[][] visited;

    private int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        m = image.length;
        n = image[0].length;
        visited = new boolean[m][n];
        dfs(image, sr, sc, image[sr][sc], newColor);
        return image;
    }

    private void dfs(int[][] image, int i, int j, int src, int target) {
        if (i < 0 || i >= m || j < 0 || j >= n) {
            return;
        }
        if (visited[i][j] || image[i][j] != src) {
            return;
        }
        visited[i][j] = true;
        image[i][j] = target;
        dfs(image, i + 1, j, src, target);
        dfs(image, i - 1, j, src, target);
        dfs(image, i, j + 1, src, target);
        dfs(image, i, j - 1, src, target);
    }
}
